﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FunnyFunction
{
    class LeetCode
    {
        public static bool IsMatch(string s, string p)
        {
            int si = 0;
            for (int i = 0; i < p.Length; i++)
            {
                if (si >= s.Length)
                    return false;

                var pc = p[i];
                var sc = s[si];
                if (pc == '.')
                {
                    si++;
                    continue;
                }
                if (pc == '*')
                {
                    if (i == p.Length - 1)
                        return true;
                    else
                    {
                        var next = p[i + 1];
                        while (true)
                        {
                            if (s[si++] == next)
                            {
                                si--;
                                break;
                            }
                            if (si >= s.Length)
                                return false;
                        }
                    }
                }
                else
                {
                    if (pc == sc)
                    {
                        si++;
                        continue;
                    }
                    else
                        return false;
                }
            }
            return si == s.Length;
        }

        // 11题 盛水最多的容器
        public static int MaxArea(int[] height)
        {
            var max = 0;
            for (int i = 0; i < height.Length - 1; i++)
            {
                for (int j = i + 1; j < height.Length; j++)
                {
                    var x = j - i;
                    var y = Math.Min(height[i], height[j]);
                    var num = x * y;
                    if (num > max)
                        max = num;
                }
            }
            return max;
        }
        //20 有效的括号
        public static bool IsValid(string s)
        {
            List<char> list= new List<char>();
            foreach (var c in s)
            {
                if (c == '(' || c == '[' || c == '{')
                    list.Add(c);
                else if (list.Count == 0)
                    return false;
                else
                {
                    var last = list.Last();
                    if ((c == ')' && last == '(')
                        || (c == ']' && last == '[')
                        || (c == '}' && last == '{'))
                        list.RemoveAt(list.Count - 1);
                    else
                        return false;
                }
            }
            return list.Count == 0;
        }

        public static int LongestValidParentheses(string s)
        {
            int maxLength = 0;
            int length = 0;
            List<char> list = new List<char>();
            int st = 0;
            for (int i = 0; i < s.Length; i++)
            {
                var c = s[i];
                if (c == '(' || c == '[' || c == '{')
                    list.Add(c);
                else if (list.Count == 0)
                {
                    maxLength = Math.Max(maxLength, length);
                    length = 0;
                }
                else
                {
                    var last = list.Last();
                    if ((c == ')' && last == '(')
                        || (c == ']' && last == '[')
                        || (c == '}' && last == '{'))
                    {
                        list.RemoveAt(list.Count - 1);
                        length += 2;
                    }
                    else
                    {
                        maxLength = Math.Max(maxLength, length);
                        length = 0;
                        st = i;
                    }
                }
            }
            return Math.Max(maxLength, length);
        }

        //217 存在重复元素
        public static bool ContainsDuplicate(int[] nums)
        {
            return nums.Distinct().Count() < nums.Length;
        }

        // 53 最大子数组和
        public static int MaxSubArray(int[] nums)
        {
            /* 动态规划
             * 1. 将题目理解为：求以某个元素为结尾的子数组的和
             * 2. 那么，以 [N]为结尾的和，要么就是自己，要么就是以[N-1]为结尾的子数组再加上[N]
             * 3. 比较上诉两个值，得出其最大值，就是以[N]为结尾的最大子数组
             * 4. 再来就是递归的解法了
             */
            var dp = new int[nums.Length];
            dp[0] = nums[0];
            int max = dp[0];
            for (int i = 1; i < nums.Length; i++)
            {
                dp[i] = Math.Max(dp[i - 1] + nums[i], nums[i]);

                max = Math.Max(dp[i], max);
            }
            return max;
        }

        // 3. 无重复子字符串
        public static int LengthOfLongestSubstring(string s)
        {
            /* 解法：滑动窗口
             * 建立一个List，一个一个字母向里面加
             * 如果出现重复，则从第一个开始删除，一直删除到没有重复
             * 每次都记录数组的最大长度
             */
            List<char> mList = new List<char>();
            int max = 0;
            for (int i = 0; i < s.Length; i++)
            {
                var ec = s[i];
                if (mList.Contains(ec))
                {
                    while (mList.Contains(ec))
                        mList.RemoveAt(0);
                }

                mList.Add(ec);
                max = Math.Max(max, mList.Count);

            }
            return max;
        }

        // 4. 寻找中位数
        public static double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            /* 指针Index1， index2
             * 分别指向开头，那个小，就移动哪个
             * 总共移动次数为 (m+n)/2
             */
            if (nums1.Length < 1 && nums2.Length < 1)
                return 0.0;
            else if (nums1.Length < 1)
            {
                if (nums2.Length % 2 == 0)
                    return (nums2[nums2.Length / 2] + nums2[nums2.Length / 2 - 1]) / 2.0;
                else
                    return nums2[nums2.Length / 2];
            }
            else if (nums2.Length < 1)
            {
                if (nums1.Length % 2 == 0)
                    return (nums1[nums1.Length / 2] + nums1[nums1.Length / 2 - 1]) / 2.0;
                else
                    return nums1[nums1.Length / 2];
            }
            int index1 = 0;
            int index2 = 0;
            int ln = 0;
            int lnn = 0;
            int mv = 0;
            while (mv <= (nums1.Length + nums2.Length) / 2)
            {
                mv++;
                if (index1 > nums1.Length - 1)
                {
                    lnn = ln;
                    ln = nums2[index2];
                    index2++;
                }
                else if (index2 > nums2.Length - 1)
                {
                    lnn = ln;
                    ln = nums1[index1];
                    index1++;
                }
                else if (nums1[index1] < nums2[index2])
                {
                    lnn = ln;
                    //ln = nums1[index1];
                    if (index1 < nums1.Length)
                    {
                        ln = nums1[index1];
                        index1++;
                    }
                    else
                    {
                        ln = nums2[index2];
                        index2++;
                    }
                }
                else
                {
                    lnn = ln;
                    if (index2 < nums2.Length)
                    {
                        ln = nums2[index2];
                        index2++;
                    }
                    else
                    {
                        ln = nums1[index1];
                        index1++;
                    }
                }
            }
            if ((nums1.Length + nums2.Length) % 2 == 0)
            {
                return (ln + lnn) / 2.0;
            }
            else
                return ln;
        }

        //88. 合并两个有序数组
        public static void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            /* 定义两个指针，分别指向数组的结尾
             * 将大的那个从nums1的尾部开始插入
             */
            int i1 = m-1;
            int i2 = n-1;
            int mv = 0;
            while (mv < m + n)
            {
                if (i1 < 0)
                {
                    nums1[m + n - 1 - mv] = nums2[i2];
                    i2--;
                }
                else if (i2 < 0)
                {
                    nums1[m + n - 1 - mv] = nums1[i1];
                    i1--;
                }
                else
                {
                    var n2 = nums2[i2];
                    var n1 = nums1[i1];

                    if (n2 > n1)
                    {
                        nums1[m + n - 1 - mv] = n2;
                        i2--;
                    }
                    else
                    {
                        nums1[m + n - 1 - mv] = n1;
                        i1--;
                    }
                }
                mv++;
            }
        }
    }
}
